package heap;

import java.util.ArrayDeque;
import java.util.PriorityQueue;
import java.util.Queue;

public class 根据字符出现的顺序排序_451 {
    public static String frequencySort(String s) {
        // z 的ascii  为 123
        int[] sc = new int[123];
        for (int i = 0; i < s.length(); i++) {
            sc[s.charAt(i)]++;
        }
        Queue<int[]> charCntPairs = new PriorityQueue<>((a, b) -> b[0]-a[0]);
        for (int i = 0; i < sc.length; i++) {
            int cnt = sc[i];
            if (cnt > 0) {
                // 注意  用这种形式来代替对象pair
                charCntPairs.offer(new int[]{cnt, i});
            }
        }
        StringBuffer sb = new StringBuffer();
        while (!charCntPairs.isEmpty()){
            int[] charCntPair = charCntPairs.poll();
            for (int i = 0; i < charCntPair[0]; i++) {
                sb.append((char)(charCntPair[1]));
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(frequencySort("tree"));
    }


    static class MaxHeap{
        int[][] heapData;
        int heapSize = 0;


        public MaxHeap() {
            // 键值对形式  难以用这种形式实现堆
            //this.heapData = new int[122];
        }


        public void buildHeap() {
            for(int i = heapSize / 2 - 1; i >= 0; i--) {
                heapify(i);
            }

        }
        private void heapify(int i) {
            int right = (i+1) << 1 ;
            int left = right - 1;
            int max = i;
            if(right < heapSize && heapData[right][0] > heapData[max][0]) {
                max = right;
            }

            if(left < heapSize && heapData[left][0] > heapData[max][0]) {
                max = left;
            }
            if(max == i) return;

            swap(max, i);
            heapify(max);
        }

        private void swap(int max, int i) {
            // a = a + b   b = a + b  - 2 * b = a - b    a = (a - b) / 2   b =  a + b
            /*heapData[max] += heapData[i];
            heapData[i] = heapData[max] - 2 * heapData[i];
            heapData[max] = (heapData[max] - heapData[i]) >> 1;
            heapData[i] += heapData[max];*/
        }
    }
}
